

//321.拼接最大数
class Solution {
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        //就是一个简单的单调栈,遍历数组,栈中元素是单调递减的即可
        int n=nums.size();
        vector<int> ret;   //用数组模拟栈
        for(int i=0;i<n;i++)
        {
            while(!ret.empty()&&ret.back()<nums[i]&&(n-i)+ret.size()>k)  //(n-i)+ret.size()>k保证栈中的元素+后面的元素>k
            {
                ret.pop_back();
            }

            ret.push_back(nums[i]);
        }
        ret.resize(k);
        return ret;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {        
        int n1=nums1.size(),n2=nums2.size();
        vector<int> ret;

        
        for(int i=0;i<=k&&i<=n1;i++)
        {
            if(n1<i) break;
            if(n2<k-i) continue;
            vector<int> tmp1=mostCompetitive(nums1,i);
            vector<int> tmp2=mostCompetitive(nums2,k-i);
            auto compare=[&](int _p,int _q)  //对两个数组从_p和_q位置后开始比较
            {
                while(_p<i&&_q<k-i&&tmp1[_p]==tmp2[_q]) _p++,_q++;  //找不同的位置
                if(_p==i) return false;
                if(_q==k-i) return true;

                return tmp1[_p]>tmp2[_q];
            };

             vector<int> each;
            int p = 0, q = 0;
            while (p < i && q < k - i)
            {
                if (compare(p,q)) each.push_back(tmp1[p++]);
                else each.push_back(tmp2[q++]);
            }
            while (p < tmp1.size()) each.push_back(tmp1[p++]);
            while (q < tmp2.size()) each.push_back(tmp2[q++]);

            if(each>ret) ret=each;
        }
        return ret;
    }
};